#pragma once
#include <iostream>
#include <vector>
using namespace std;

namespace test
{

template<size_t N>
class bitset
{
public:
    bitset()
    {
        _bits.resize(N / 8 + 1);
    }

    void set(size_t e)
    {
        size_t i = e / 8;
        size_t j = e % 8;

        _bits[i] |= (1 << j);
    }

    void reset(size_t e)
    {
        size_t i = e / 8;
        size_t j = e % 8;

        _bits[i] &= ~(1 << j);
    }

    bool test(size_t e)
    {
        size_t i = e / 8;
        size_t j = e % 8;

        return _bits[i] & (1 << j);
    }

private:
    vector<char> _bits;
};

template <size_t N>
class TwoBitSet
{
    bitset<N> _bs1;
    bitset<N> _bs2;
public:
    void set(size_t e)
    {
        if (!_bs2.test(e))
        {
            _bs1.set(e);
            _bs2.set(e);
        }
        else
        {
            _bs1.reset(e);
        }
    }
    vector<int> result()
    {
        vector<int> v;
        for (int i = 0; i < N; i++)
            if (_bs1.test(i)) v.push_back(i);
        return v;
    }
};

void handle_question_1()
{
    //bitset<(size_t)-1> bs1;
    //bitset<0effffffff> bs2;

    int a[] = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
        31, 32, 33, 34, 35, 36, 37, 38, 39, 39, 40, 41, 42, 43, 44,
        45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
        60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 69, 69, 70, 71, 72,
        73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,
        88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 99, 99, 99,
    };
    TwoBitSet<1000> tbs;

    for (auto e : a)
    {
        tbs.set(e);
    }

    vector<int> res = tbs.result();
    for (auto e : res)
    {
        cout << e << " ";
    }
    cout << endl;
}

template<size_t N>
void handle_question_21(vector<int>& v1, vector<int>& v2, vector<int>& res)
{
    bitset<N> bs;

    for (auto e : v1)
    {
        bs.set(e);
    }

    for (auto e : v2)
    {
        if (bs.test(e))
        {
            res.push_back(e);
            bs.reset(e);
        }
    }
}

template<size_t N>
void handle_question_22(vector<int>& v1, vector<int>& v2, vector<int>& res)
{
    bitset<N> bs1;
    bitset<N> bs2;

    for (auto e : v1)
    {
        bs1.set(e);
    }

    for (auto e : v2)
    {
        bs2.set(e);
    }

    for (int i = 0; i < N; i++)
    {
        if (bs1.test(i) && bs2.test(i))
        {
            res.push_back(i);
        }
    }
}

template <size_t N>
class TwoBitSet_2
{

    vector<int> result()
    {
        vector<int> v;
        for (int i = 0; i < N; i++)
        {
            //if (!_bs1.test(i) || !_bs2.test(i))

        }
        return v;
    }
};

template<size_t N>
void handle_question_3()
{
    vector<int> v = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
        31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
        46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
        61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,
        76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
        91, 92, 93, 94, 95, 96, 97, 98, 99, 99, 99
    };

    bitset<N> _bs1;
    bitset<N> _bs2;

    for (auto e : v)
    {
        if (!_bs1.test(e) && !_bs2.test(e)) // 00 -> 10
        {
            _bs1.set(e);
        }
        if (_bs1.test(e) && !_bs2.test(e)) // 10 -> 01
        {
            _bs1.reset(e);
            _bs2.set(e);
        }
        if (!_bs1.test(e) && _bs2.test(e)) // 01 -> 11
        {
            _bs1.set(e);
            _bs2.set(e);
        }
    }

    for (int i = 0; i < N; i++)
    {
        if ((_bs1.test(i) && !_bs2.test(i))
        || (!_bs1.test(i) && _bs2.test(i)))
        {
            v.push_back(i);
        }
    }
}

void test_bit_set()
{
    //handle_question_1();

    vector<int> v1 = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
        16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
        31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
        46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
        61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,
        76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
        91, 92, 93, 94, 95, 96, 97, 98, 99,
    };

    vector<int> v2 = {
        0, 3, 4, 7, 9,
    };

    vector<int> res;
    // handle_question_21<100>(v1, v2, res);
    // handle_question_22<100>(v1, v2, res);

    for (auto e : res)
    {
        cout << e << " ";
    }
    cout << endl;

    handle_question_3<100>();
}

}
